/**
 删除节点
 */

// 19. 删除链表的倒数第 N 个结点
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    let dummyHead = ListNode(0)
    dummyHead.next = head
    var slow: ListNode? = dummyHead, fast = slow, m = n
    while m > 0 {
        fast = fast?.next
        m -= 1
    }
    while fast?.next != nil {
        slow = slow?.next
        fast = fast?.next
    }
    slow?.next = slow?.next?.next
    return dummyHead.next
}

// 83. 删除排序链表中的重复元素
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
    var pre = head
    while pre?.next != nil {
        let temp = pre?.next
        if pre?.val == temp?.val {
            pre?.next = pre?.next?.next
        } else {
            pre = pre?.next
        }
    }
    return head
}

// 82. 删除排序链表中的重复元素2
func deleteDuplicates2(_ head: ListNode?) -> ListNode? {
    let dummyHead = ListNode(0)
    dummyHead.next = head
    var p: ListNode? = dummyHead
    while p?.next != nil {
        var q = p?.next, n = 0
        while q?.val == q?.next?.val {
            q = q?.next
            n += 1
        }
        if n == 0 {
            p?.next = q
            p = q
        } else {
            p?.next = q?.next
        }
    }
    return dummyHead.next
}

var head = ListNode(1)
//head.next = ListNode(2)
//head.next?.next = ListNode(3)
//head.next?.next?.next = ListNode(4)
//head.next?.next?.next?.next = ListNode(5)

head.next = ListNode(1)
head.next?.next = ListNode(2)
head.next?.next?.next = ListNode(3)

ListNode.printNode(head)
//head = removeNthFromEnd(head, 3) ?? ListNode(-1)
head = deleteDuplicates2(head) ?? ListNode(-1)
ListNode.printNode(head)
